package de.fuberlin.inf.alp3.ue09.a2;

public class GraphImpl implements Graph {
    float[][] adjacency;
    Path[][] shortestPaths;
    
    public GraphImpl (int max) {
        adjacency = new float[max][max];
        this.shortestPaths = null;
        for (int i = 0; i < adjacency.length; i++)
            for (int k = 0; k < adjacency[i].length; k++)
                if (i == k)
                    adjacency[i][k] = 0.0F;
                else
                    adjacency[i][k] = Float.MAX_VALUE;
    }

    @Override
    public void add(int a, int b, float w) throws IllegalArgumentException {
        if ((w < 0) || (a > adjacency.length) || (b > adjacency.length))
            throw new IllegalArgumentException();
        // empty Cache
        this.shortestPaths = null;
        a--; b--;
        adjacency[a][b] = adjacency[b][a] = w;
    }
    
    @Override
    public Path shortestPath(int a, int b) throws IllegalArgumentException {
        if ((a == b) || (a < 1) || (b < 1) || (a > adjacency.length) ||
                (b > adjacency.length))
            throw new IllegalArgumentException();
        if (shortestPaths == null)
            floyd();
        return shortestPaths[--a][--b];
    }

    private void floyd() {
        this.shortestPaths = new Path[adjacency.length][adjacency.length];
        for (int i = 0; i < adjacency.length; i++)
            for (int j = 0; j < adjacency.length; j++)
                shortestPaths[i][j] = (new Path(i, j, adjacency[i][j]));
        for (int i = 0; i < adjacency.length; i++)
            extend(i);
    }

    private void extend(int i) {
        for(int j = 0; j < shortestPaths.length; j++)
            for(int k = 0; k < shortestPaths.length; k++)
                if ((shortestPaths[j][i].cost + shortestPaths[i][k].cost) <
                        shortestPaths[j][k].cost) {
                    int[] path = new int[shortestPaths[j][i].path.length + 
                                         shortestPaths[i][k].path.length - 1];
                    int x = 0;
                    for (; x < shortestPaths[j][i].path.length; x++)
                        path[x] = shortestPaths[j][i].path[x];
                    for (; (x - shortestPaths[j][i].path.length) < 
                            (shortestPaths[i][k].path.length - 1); x++)
                        path[x] = shortestPaths[i][k].path[x - 
                                         (shortestPaths[j][i].path.length - 1)];
                    shortestPaths[j][k] = new Path(path,
                        (shortestPaths[j][i].cost + shortestPaths[i][k].cost));
                }
    }
}